/*
 * @lc app=leetcode.cn id=798 lang=cpp
 *
 * [798] 得分最高的最小轮调
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
//差分数组法
    int bestRotation(vector<int>& nums) {
        //元素 x 记 1 分的下标范围是 [x, n - 1]
        // 则当轮调下标为 k 时，元素 x 位于下标 (i - k + n) mod n
        //x <= (i - k + n) mod n,则加一分，等价于 K <= (i - x +n) mod n
        //由于元素 x 记 1 分的下标有 n - x个，因此有 k <= (i + 1) mod n
        int n = nums.size();
        vector<int> diffs(n);
        for (int i = 0; i < n; i++) {
            int low = (i + 1) % n;
            int high = (n + i + 1 - nums[i]) % n;
            diffs[low]++;
            diffs[high]--;
            if (low >= high) {
                //初始的值
                diffs[0]++;
            }
        }
        int bestIndex = 0;
        int maxScore = 0;
        int score = 0;
        for (int i = 0; i < n; i++) {
            score += diffs[i];
            if (score > maxScore) {
                bestIndex = i;
                maxScore = score;
            }
        }
        return bestIndex;
    }
};
// @lc code=end

//暴力法超时，需要优化剪枝
// int n = nums.size();
//         vector<int> record(n,0);
//         int max_index = INT32_MIN;
//         for(int k = 0;k < n;k++) {
//             for(int j = 0;j < n;j++) {
//                 int isBigger= (j < k)? (nums[j]-(j+n-k)):(nums[j]-(j-k));
//                 record[k] += (isBigger <= 0)? 1:0;
//             }
//             max_index = max(max_index,record[k]);
//         }
//         for(int i = 0;i < n;i++) {
//             if(record[i] == max_index) {
//                 return i;
//             }
//         }
//         return 0;